Goltz đã chào đời tại Bielkenfeld, Đông Phổ (sau đổi tên thành Goltzhausen; ngày nay là Ivanovka, ở Polessk, tỉnh Kaliningrad của Nga),[5] trong một gia đình quý tộc đã sa sút. Ông sinh trưởng tại thái ấp Fabiansfelde gần Preußisch Eylau, mà cha ông đã mua vào năm 1844.[6] Cha đã phục vụ Quân đội Phổ trong khoảng 19 năm mà không hề vượt được qua cấp trung úy, và những nỗ lực trồng trọt của ông cũng nhận thất bại tương tự. Về sau, ông qua đời do bệnh dịch tả trong một chuyến đi đến Danzig (ngày nay là Gdańsk) khi Colmar mới 6 tuổi.[7]

Goltz đã gia nhập lực lượng bộ binh Phổ năm 1861 với quân hàm thiếu úy trong Trung đoàn Bộ binh số 41 (Đông Phổ số 5), đóng quân ở Königsberg (Kaliningrad ngày nay).[8] Vào năm 1864 tại Thorn (Toruń), sau đó ông tham gia Học viện Quân sự Berlin, nhưng tạm thời rút lui vào năm 1866 để phục vụ quân đội trong cuộc Chiến tranh Áo-Phổ. Trong cuộc chiến này, ông bị thương tại Trautenau. Vào năm 1867, ông gia nhập Cục Đo đạc địa hình của Bộ Tổng tham mưu, và khi cuộc Chiến tranh Pháp-Đức (1870 – 1871), ông gia nhập bộ tham mưu của Hoàng thân Friedric Karl, tướng tư lệnh của Binh đoàn thứ hai của Phổ. Ông đã tham chiến trong các trận đánh tại Vionville và Gravelotte, và trong cuộc vây hãm Metz. Sau khi Metz thất thủ, ông phụng sự dưới quyền Hoàng tử Đỏ trong chiến dịch sông Loire, tham gia trong các trận đánh tại Orléans và Le Mans.

Goltz đã được bổ nhiệm làm giáo sư tại trường quân sự ở Potsdam vào năm 1871, được phong quân hàm Đại úy, và được vào một chân trong Cục Sử học Bộ Tổng tham mưu. Chính trong giai đoạn này, ông đã viết Die Operationen der II. Armee bis zur Capitulation von Metz (Các chiến dịch của Binh đoàn thứ hai đến khi Metz đầu hàng) và Die Sieben Tage von Le Mans (Bảy ngày tại Le Mans), đều được xuất bản vào năm 1873. Năm 1874, ông được bổ nhiệm làm sĩ quan tham mưu trưởng thứ nhất (Ia) của Sư đoàn số 6, và trong khi giữ cương vị này ông viết Die Operationen der II. Armee an der Loire (Các chiến dịch của Binh đoàn thứ hai trên sông Loire, xuất bản năm 1875) và Léon Gambetta und seine Armeen (Léon Gambetta và các đạo quản của mình, xuất bản năm 1877). Tác phẩm Léon Gambetta und seine Armeen cũng được dịch sang tiếng Pháp vào năm 1877, và nhiều sử gia xem đây là tác phẩm lý luận quân sự độc đáo nhất của ông.

Goltz đã nhấn mạnh rằng, bất chấp chiến thắng nhanh chóng ban đầu của quân đội Đức trước Đế chế Pháp trong trận Sedan, nền Cộng hòa Pháp mới được thành lập đã động viên được tinh thần dân chúng để tiến hành một Volkskrieg ("Chiến tranh Nhân dân") kéo dài cuộc Chiến tranh Pháp-Đức thêm vài tháng nữa (Cuộc vây hãm Paris, chiến dịch sông Loire và các hoạt động du kích đằng sau chiến tuyến của quân Đức, trong đó riêng quân du kích Pháp đã kìm hãm 20% binh lực của Đức). Từ đó, ông kết luận rằng trong bất kỳ cuộc chiến tranh nào trương tương lại, dự đoán về một thắng lợi nhanh gọn trước Pháp là viễn vông. Các quan điểm mà Goltz bày tỏ trong Léon Gambetta und seine Armeen đã khiến cho những người có thế lực không ưa chuộng ông và dẫn đến việc ông bị điều về phục vụ ở cấp trung đoàn trong một thời gian, nhưng không lâu sau đó ông trở lại Cục Lịch sử Quân sự. Vào năm 1878, Goltz được bổ nhiệm làm giảng viên lịch sử quân sự tại học viện quân sự ở Berlin, giữ chức vụ này trong vòng 5 năm và được thăng quân hàm Thiếu tá. Vào năm 1883, ông cho ra mắt Roßbach und Jena (một ấn bản mới và đã duyệt lại, Von Rossbach bis Jena und Auerstadt, 1906), Das Volk in Waffen (Cả nước vũ trang) – cả hai đều trở thành những tác phẩm kinh điển, và trong thời gian cư ngụ của mình tại Berlin ông đã đăng nhiều bài báo trên các tạp chí quân sự.